#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include <linux/futex.h>
#include <sys/time.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <limits.h>
#include <math.h>

/* Número de vezes que uma thread deve entrar na região crítica. */
#define VEZES 15
#define TESTE 8
#define SLP_T 0
#define TODOS LONG_MAX
#define DEBUG 1

typedef struct duelo
{
   int disputa; /* round da disputa */
   short interesse[2];
   int ultimo;
} duelo;

/* resultado dos duelos */
volatile duelo *esp;

/* futex para resetar partida */
volatile int reset;

/* recurso compartilhado */
volatile int s;

/* numero de rounds - apenas leitura */
int round_max;

/* numero de threads */
int n;

/* Retorna -1 se o futex não bloqueou e 
            0 caso contrário */
int futex_wait(void *addr, int val1) {
  return syscall(SYS_futex, addr, FUTEX_WAIT, 
                 val1, NULL, NULL, 0);
}

/* Retorna o número de threads que foram acordadas */
int futex_wake(void *addr, int n) {
    return syscall(SYS_futex, addr, FUTEX_WAKE, 
                   n, NULL, NULL, 0);
}

void zera_duelo(duelo* d, int round)
{
   d->disputa = round;
   d->ultimo = -1;
   d->interesse[0] = d->interesse[1] = 0;
}

void reseta_duelos()
{
   int i;
   int tam = (n + 1) / 2;
   for (i = 0; i < tam; i++)
   {
      zera_duelo((duelo*)&esp[i], 1);
   }
}

void* f_thread(void *id)
{
   int p, pp, n_id, i, round, ganhei;

   for (i = 0; i < VEZES; i++)
   {
      round = 1;
      ganhei = 0;
      n_id = (int)id;

      while (round < round_max)
      {
         /* sleep entre rounds */
         sleep(SLP_T);         

         /* calcula onde buscar duelo */
         p = n_id/2;

         /* calcula qual minha posicao dentro do duelo */
         pp = n_id % 2;
         
         /* define novo id */
         n_id = p;
         
         /* se essa disputa nao acontece no meu round */
         if (esp[p].disputa != round)
            futex_wait((void*)&esp[p].disputa, esp[p].disputa); /* espero que a disputa anterior termine */         
         
         if (DEBUG)
            printf("Round: %d. Duelando id: %d. Posicao: %d. Pp: %d. Interesse: %d. OutroInteresse: %d\n", round, (int)id, p, pp, esp[p].interesse[pp], esp[p].interesse[!pp]);

         /* levanto interesse e marco que fui o ultimo */
         esp[p].interesse[pp] = 1;
         esp[p].ultimo = (int)id;

         round++;               

         /* se eu me interessei por ultimo, mas outro jah tinha interesse */
         if (esp[p].ultimo == (int)id && esp[p].interesse[!pp])
         {
            if (DEBUG)
               printf("Round: %d. DEVO ESPERAR, id: %d\n", round-1, (int)id);
            /* informa para ganhadora que jah sei do resultado */
            futex_wake((void*)&esp[p].interesse[pp], TODOS);

            futex_wait((void*)&reset, 0);       /* perdi, espero acabar partida */            
            ganhei = 0;
            break;
         }
         else         
         {
            /*espera thread adversaria saber que perdeu */
            /* if (!esp[p].interesse[!pp])
            {
               printf("Esperando outro saber, id: %d\n", (int)id);
               futex_wait((void*)&esp[p].interesse[!pp], 0);
               printf("Outro jah sabe, id: %d\n", (int)id);
               }*/
            while(!esp[p].interesse[!pp]);

            ganhei = 1;

            if (DEBUG)
               printf("Round: %d. Ganhei id: %d. Posicao: %d. Interesse outro: %d\n", round-1, (int)id, p, esp[p].interesse[!pp]);


            /* informo fim da disputa */
            zera_duelo((duelo*)&esp[p], round);        /* ganhei, limpa duelo para prox round */
            /* acordo quem esperava o fim da disputa, espera-se apenas que no maximo uma thread acorde */
            futex_wake((void*)&esp[p].disputa, TODOS);
         }
      }

      if (ganhei)
      {
         /* regiao critica */
         
         s = (int)id;
         /* sleep entre atribuicao e impressao */
         sleep(SLP_T);
         printf("Thread %d, s = %d.\n", (int)id, s);
         
         /* reseta */
         reseta_duelos();
         futex_wake((void*)&reset, TODOS);

         /* fim regiao critica */
         /*sleep fora da regicao critica */
         sleep(SLP_T);
      }
   }

   return NULL;
}

int main(int argn, char** argv)
{
   pthread_t *thrv;
   int i, tam;

   n = TESTE;
   tam = (n + 1) / 2;
   reset = 0;
   round_max =  (int)log2(n) + 1;
   
   esp = (duelo*)malloc(sizeof(duelo)*tam);
   thrv = (pthread_t*)malloc(sizeof(pthread_t)*n);   

   reseta_duelos();

   for (i = 0; i < n; i++)
   {
      pthread_create(&thrv[i], NULL, (void*)f_thread, (void*)i);
   }

   for (i = 0; i < n; i++)
   {
      pthread_join(thrv[i], NULL); 
   }

   free((void*)esp);
   free(thrv);
   return 0;
}





